算法设计------Binary Indexed Tree

举个栗子

为了方便理解Binary Indexed Tree,考虑以下问题：

对于数组 arr[1…n]，执行以下两种操作:

getSum()操作：计算前i个元素的和。

update()操作：改变第i个元素的值，arr[i] = x (1 <= i <= n)。

两个简单的解决方案

方案一：通过遍历数组计算前i个元素的和O( n )的时间复杂度。更新元素直接赋值O( 1 )的时间复杂度。

方案二：创建另一个数组，并在这个数组的第i个索引存储从开始到结束的总和。可以在O（1）时间内计算给定范围的总和，但是更新操作需要O（n）个时间。

两种方案在需操作数组量很大的情况下，都不是很理想，有什么方案能让两种操作都在O（log n）的时间复杂度内完成呢？。

Binary Indexed Tree（树状数组）

Binary Indexed Tree 基于“所有的正整数都可以表示为2的幂的和”这样的事实（例如，5可以表示为4 + 1），巧妙的将数组进行分割。为上述问题提供了两种操作时间复杂度都控制在O(Log n )的方案。

图解

Binary Indexed Tree 以数组的形式表示（所以又叫树状数组），记为BITree[]。BITree[]中的元素个数与初始数组arr[]一致。 BITree[]中每个元素存储arr[]的某些元素的总和。

getSum() & update() 实现分析

为方便讨论假定数组下标从1开始，为更清晰的看到规律，我们以二进制的形式表示数组下标。

getSum()分析

分析以下求和操作：

求和getSum（4）： getSum( 0100 ) = BITree [ 0100 ] .

求和getSum（5）：getSum( 0101 ) = BITree [ 0101 ] + BITree [ 0100 ]。

求和getSum（7）：getSum( 0111 ) = BITree [ 0111 ] + BITree [ 0110 ] + BITree [ 0100 ] 。

求和getSum（11）：getSum( 1011 ) = BITree [ 1011 ] + BITree [ 1010 ] + BITree [ 1000 ] 。

可以看到getSum(i) 的结果可以通过x个BITree元素求和获得，且遵循以下规律：

x等于 i二进制表示下位值为1的数量。
待求和BITree元素下标可通过迭代i = i - (i & (-i))获得，即从右往左将所有为1的二进制位置为0。（i & (-i) 返回 i 的二进制数最低位为１的权值）。

update()分析

update（1）: update（0001）——> update (0010) ——>update(0100)——>update(1000)

update（3）: update（0011）——> update (0010) ——>update(0100)——>update(1000)

update（5）: update（0101）——> update (0110) ——>update(1000)

当我们更新第i个元素，直接受影响的下标可通过将i 加上i的最位为1的权值获得，受影响的元素下标可通过迭代i = i + (i & (-i))获得。

Binary Indexed Tree 可视化演示

可视化演示

代码实现

.h 文件

#include <stdio.h>

int getSum(int BITree[], int index);//求和
void updateBIT(int BITree[], int n, int index, int val);//更新BITree的第n个节点
int *constructBITree(int arr[], int n);//构建BITree

#endif /* BITree_h */

.m文件

#include "BITree.h"
#include "stdlib.h"

int getSum(int BITree[], int index)
{
    int sum = 0;
    
    //迭代求和
    while (index>0)
    {
        sum += BITree[index];
        index -= index & (-index);
    }
    return sum;
}

void updateBIT(int BITree[], int n, int index, int val)
{
    // 迭代更新所有相关元素
    while (index < n)
    {
        BITree[index] += val;
        index += index & (-index);
    }
}

int *constructBITree(int arr[], int n)
{

    int * BITree = malloc(sizeof(int) * (n));
    for (int i=0 ; i<n; i++)
        BITree[i] = 0;
    
    // 更新BITree，从1开始为有效数据
    for (int i=1; i< n; i++)
        updateBIT(BITree, n, i, arr[i]);
    
    return BITree;
}

测试代码

void testBITree(){
    //第0 个元素为无效元素
    int freq[] = {0,2, 1, 5, 7, 9, 5, 8, 9, 4, 2, 9};
    int n = sizeof(freq)/sizeof(freq[0]);
    int *BITree = constructBITree(freq, n);
    
    printf("Sum of elements in arr[1..5] is %d\n",getSum(BITree, 11));

    // 更新操作
    freq[3] += 6;
    updateBIT(BITree, n, 3, 6); //更新
    printf("After update Sum of elements in arr[1..5] is %d\n",getSum(BITree, 11));

}

执行结果

1 2	Sum of elements in arr[1..5] is 61 After update Sum of elements in arr[1..5] is 67